package oj0515.oj0515_01;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class BiNode {
    char data; //结点的数据值
    BiNode lchild;//结点的左孩子
    BiNode rchild;//结点的右孩子

    BiNode(char data) {
        this.data = data;
        this.lchild = null;
        this.rchild = null;
    }
}

class BiTree {
    private int index;
    private String str;
    private BiNode root;

    public BiTree(String str) {
        this.index = 0;//作为扫描字符串的索引
        this.str = str;//初始输入字符串
        this.root = create();//root为根节点的引用
    }
    //返回根节点的引用, 开放给外部调用
    public BiNode getRoot(){
        return this.root;
    }
    //创建树方法已经写好，无需修改
    private BiNode create() {
        char ch = str.charAt(index);
        if (ch == '#') {
            index++;
            return null;//建立一棵空树
        }
        BiNode bt = new BiNode(ch);
        index++;
        bt.lchild = create(); //递归建立左子树
        bt.rchild = create(); //递归建立右子树
        return bt;
    }

    public void preOrder(BiNode bt) {
        //递归调用的结束条件
        //访问根结点bt的数据域
        //前序递归遍历bt的左子树
        //前序递归遍历bt的右子树
        if(bt == null) return;
        System.out.print(bt.data + " ");
        preOrder(bt.lchild);
        preOrder(bt.rchild);
    }

    public void inOrder(BiNode bt) {
        //递归调用的结束条件
        //中序递归遍历bt的左子树
        //访问根结点bt的数据域
        //中序递归遍历bt的右子树
        if(bt == null) return;
        inOrder(bt.lchild);
        System.out.print(bt.data + " ");
        inOrder(bt.rchild);
    }

    public void postOrder(BiNode bt) {
        //递归调用的结束条件
        //后序递归遍历bt的左子树
        //后序递归遍历bt的右子树
        //访问根结点bt的数据域
        if(bt == null) return;
        postOrder(bt.lchild);
        postOrder(bt.rchild);
        System.out.print(bt.data + " ");
    }

    public void leverOrder() {
        //创建一个队列，用于存储二叉树的结点
        //将根节点入队
        //当队列不为空时，执行以下操作：
        //将队头结点出队，并访问其数据域
        //如果该结点的左孩子不为空，将其左孩子入队
        //如果该结点的右孩子不为空，将其右孩子入队s
        if (root == null) return;
        Queue<BiNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            BiNode bt = queue.poll();
            System.out.print(bt.data + " ");
            if (bt.lchild != null) queue.add(bt.lchild);
            if (bt.rchild != null) queue.add(bt.rchild);
        }
    }
}

public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();
        BiTree biTree = new BiTree(input);
        // 执行前序遍历，并打印遍历结果
        biTree.preOrder(biTree.getRoot());
        System.out.println();
        // 执行中序遍历，并打印遍历结果
        biTree.inOrder(biTree.getRoot());
        System.out.println();
        // 执行后序遍历，并打印遍历结果
        biTree.postOrder(biTree.getRoot());
        System.out.println();
        // 执行层序遍历，并打印遍历结果
        biTree.leverOrder();
        System.out.println();

        scanner.close();
    }
}